#!/usr/bin/env python                         # -*- coding: utf-8 -*-

__author__ = 'Jouni K. Seppänen, Siegfried Nijssen'

import bisect
import copy
import optparse
import os
import re
import sets
import stat
import sys

debugging = False

def string(value):
    if value==0: return "0"
    if value==1: return "1"
    return str(value)


def strictly_increasing(seq):
    if len(seq) == 0: return True
    prev = seq[0]
    for elt in seq[1:]:
	if not prev < elt: return False
	prev = elt
    return True

def debug(*args):
    if debugging:
	for a in args:
	    print >>sys.stderr, a,
	print >>sys.stderr

def rlookup(dict, value):
    possibilities = (x for (x,y) in dict.items() if y==value)
    try:
	return possibilities.next()
    except StopIteration:
	raise ValueError, "value %s not in dict" % value

class Matrix(object):
    __slots__ = ("rows", "columns")
    typename = "abstract"

class SparseMatrix(Matrix):
    __slots__ = ("data")
    typename = "real"

    def __init__(self, rows=0, columns=0):
	self.rows, self.columns = rows, columns
	self.data = [ {} for i in range(rows) ]

    def enlarge(self, newrows, newcols):
	self.data.extend([ {} for i in range(self.rows, newrows) ])
	self.rows, self.columns = \
	    max(self.rows, newrows), max(self.columns, newcols)

    def set(self, row, col, value):
	self.enlarge(row+1, col+1)
	rowdata = self.data[row]
	rowdata[col] = value

    def get(self, row, col):
	return self.data[row][col]

    def get_row_dict(self, row):
	return self.data[row]

    def get_row(self, row):
	d = [ 0 for i in range(self.columns) ]
	for i, value in self.data[row].items():
	    d[i] = value
	return d

    def set_sparse_row(self, row, data):
        self.enlarge(row+1, max([self.columns] + [int(x[0])+1 for x in data]))
        self.data[row] = data

class DenseMatrix(Matrix):
    __slots__ = ("data", "protorow")
    typename = "real"

    def __init__(self, rows, columns, data=None):
	self.rows, self.columns = rows, columns
	self.protorow = [ 0 for i in range(columns) ]
        if data is None:
            self.data = [ copy.copy(self.protorow) for i in range(rows) ]
        else:
            self.data = copy.deepcopy(data)

    def enlarge(self, rows):
	self.data.extend([ copy.copy(self.protorow) 
			   for i in range(self.rows, rows) ])
        self.rows = max(self.rows, rows)

    def set(self, row, col, value):
	self.enlarge(row+1)
	self.data[row][col] = value

    def set_row(self, row, values):
        self.enlarge(row+1)
        for col,v in enumerate(values):
            self.data[row][col] = v

    def get(self, row, col):
	return self.data[row][col]

    def get_row(self, row):
	return self.data[row]

    def get_row_dict(self, row):
	d = self.data[row]
	return dict([ (i, d[i]) for i in range(self.columns) 
		      if d[i] != 0 ])

class BinaryMatrix(SparseMatrix):
    typename = "binary"

    def set_sparse_row(self, row, data):
        self.enlarge(row+1, max([self.columns] + [x+1 for x in data]))
        myrow = {}
        for d in data:
           myrow[d] = 1
           self.data[row] = myrow

    def get_sparse_row(self, row):
	return sorted(self.data[row].keys())

class StringMatrix(Matrix): 
    typename = "string"
    
class ArffMatrix(Matrix):
    """Arff Matrices differ in that elements can be texts, numerical
       categorical, etc., and that there is a dictionary to determine
       which column is what, and columns can have names"""
    typename = "arff"
    __slots__ = ("dictionary","data")
    
    def __init__(self):
        self.data = []
        return
    
    def enlarge(self, rows):
        self.data.extend([ copy.copy(self.protorow) 
               for i in range(self.rows, rows) ])
        self.rows = max(self.rows, rows)

    def set(self, row, col, value):
        self.enlarge(row+1)
        self.data[row][col] = value

    def set_row(self, row, values):
        self.enlarge(row+1)
        for col,v in enumerate(values):
            self.data[row][col] = v

    def get(self, row, col):
        return self.data[row][col]

    def get_row(self, row):
        return self.data[row]

    def get_row_dict(self, row):
        d = self.data[row]
        return dict([ (i, d[i]) for i in range(self.columns) ])
    
    

class FileFormat(object):
    __slots__ = ()

    def __method(self, action, type):
	typename = getattr(type, 'typename', None)
	if typename is None:
	    raise TypeError, \
		"Type not recognized by FileFormat.__method: %s" % type
	method = getattr(self, action + "_" + type.typename, None)
	if method is None:
	    raise TypeError, "Type '%s' not representable in format %s" \
		% (type.typename, self.__class__)
	return method

    def write(self, file, ob):
	return self.__method('write', type(ob))(file, ob)

    def read(self, file):
	raise NotImplementedError

    def autodetect(self, file, fast):
	"""Guess if the file looks like it has this format. Return 0 for
	definitely not this format, 1 for definitely this format,
	floating-point number in between for uncertain cases. If fast
	is False, try harder to increase the certainty of the guess."""

	filepos = file.tell()
	debug("autodetecting", self.__class__)
	try:
	    fmt = self._autodetect(file, fast)
	finally:
	    file.seek(filepos)
	return fmt

    def _autodetect(self, file, fast):
	raise NotImplementedError

class Iq(FileFormat):
    """The official IQ file format."""
    __slots__ = ()

    readers = { '# IQ sparse boolean matrix format 0.1': 'read_binary',
		'# IQ sparse real matrix format 0.1': 'read_sparse_real',
		'# IQ dense real matrix format 0.1': 'read_dense_real',
        '% IQ arff dense matrix format 0.1': 'read_dense_arff' }
    cookies = { 'sparse boolean': rlookup(readers, 'read_binary'),
		'sparse real': rlookup(readers, 'read_sparse_real'),
		'dense real': rlookup(readers, 'read_dense_real'),
        'dense arff': rlookup(readers, 'read_dense_arff') }

    def read(self, file):
	cookie = file.readline().strip()
	method = self.readers.get(cookie, None)
	if method is None: 
	    raise TypeError, "not a recognized IQ cookie: %s" % cookie
	method = getattr(Iq, method)
	return method(self, file)

    def _autodetect(self, file, fast):
	line = file.readline().strip()
	if line in self.readers.keys():
	    debug("saw IQ cookie")
	    return 1
	else:
	    debug("not an IQ cookie:", line)
	    return 0

    def __rows_columns(self, file):
	line = file.readline()
	assert line.startswith('# rows: ')
        rows = int(line[len('# rows: '):])

	line = file.readline()
	assert line.startswith('# columns: ')
        columns = int(line[len('# columns: '):])

	return rows, columns

    def write_real(self, file, ob):
	    if isinstance(ob, SparseMatrix):
	        self.write_sparse_real(file, ob)
	    else:
	        self.write_dense_real(file, ob)
        
    def write_arff(self, file, ob): 
        file.write(self.cookies['dense arff'] + '\n')
        Arff().write_arff ( file, ob )
        
    def read_arff(self, file):
        return Arff().read(file)        

    def write_sparse_real(self, file, ob):
	file.write(self.cookies['sparse real'] + '\n')
	file.write('# rows: %d\n' % ob.rows)
	file.write('# columns: %d\n' % ob.columns)
	for i in range(ob.rows):
	    rd = ob.get_row_dict(i)
	    file.write(' '.join('%d:%f' % (int(j), value)
				for (j, value) in sorted(rd)))
	    file.write('\n')

    sparse_real_re = re.compile(r'(\d+)\s*:\s*([+-]?\d*[.]\d*(?:[eE]\d+)?)\s*')
	
    def read_sparse_real(self, file):
	rows, columns = self.__rows_columns(file)
	matrix = SparseMatrix(rows, columns)

	for i in range(rows):
	    line, pos = file.readline(), 0
	    line = line.strip()
	    while pos < len(line):
		match = Iq.sparse_real_re.match(line, pos)
		if match is None:
		    errmsg = "syntax error on row %d: %s" % (i, line[pos:])
		    raise TypeError, errmsg
		pos = match.end()
		j, value = match.groups()
		j, value = int(j), float(value)
		matrix.set(i, j, value)

	return matrix
    

    def write_dense_real(self, file, ob):
	file.write(self.cookies['dense real'] + '\n')
	file.write('# rows: %d\n' % ob.rows)
	file.write('# columns: %d\n' % ob.columns)
	for i in range(ob.rows):
	    rd = ob.get_row(i)
	    file.write(' '.join(string(value) for value in rd))
	    file.write('\n')

    def read_dense_real(self, file):
        rows, columns = self.__rows_columns(file)
        matrix = DenseMatrix(rows, columns)

        for i in range(rows):
            line = file.readline().strip()
            data = [ float(x) for x in line.split() ]
            matrix.set_row(i, data)

        return matrix

    def write_binary(self, file, ob):
	file.write(self.cookies['sparse boolean'] + '\n')
	file.write('# rows: %d\n' % ob.rows)
	file.write('# columns: %d\n' % ob.columns)
	Fimi().write_binary(file, ob)

    def read_binary(self, file):
	rows, columns = self.__rows_columns(file)
	matrix = BinaryMatrix(rows, columns)

	for i in range(rows):
	    line = file.readline()
	    line.strip()
 	    data = line.split()
	    if data == ['']:
		data = []
	    data = [ int(x) for x in data ]
	    assert strictly_increasing(data)
	    try: newcols = max(data)+1
	    except ValueError: newcols = 1
	    matrix.enlarge(i+1, newcols)
	    matrix.set_sparse_row(i, data)

	return matrix



class Spconvert(FileFormat):
    """Matlab-compatible sparse matrix format. Rows and columns are
    indexed starting from 1."""

    def _autodetect(self, file, fast):
	if fast:
	    limit = 100
	else:
	    limit = float('inf')

	lineno = 0
	while lineno < limit:
	    line = file.readline()
	    lineno += 1
	    if line == '': break
	    try:
		fields = line.split()
		assert len(fields) == 3
		int(fields[0]), int(fields[1]), float(fields[2])
	    except:
		debug("impossible spconvert line:", line)
		return 0
	
	if lineno == 0: return 0
	if not fast: return 1	# We hit EOF
	
	return float(file.tell()) / os.fstat(file.fileno())[stat.ST_SIZE]

    def read(self, file):
	ob = SparseMatrix()
	binary = True
	for line in file:
	    fields = line.split()
	    row, col, value = int(fields[0]), int(fields[1]), float(fields[2])
	    if value not in [0, 1]:
		binary = False
	    ob.set(row-1, col-1, value)

	if binary:
	    newob = BinaryMatrix(ob.rows, ob.columns)
	    newob.data = ob.data
	    ob = newob

	return ob

    def write_real(self, file, ob):
	# Start by outputting bottom-right element, defining the size
	# of the matrix.
	last_elt = ob.get(ob.rows-1, ob.columns-1)
	file.write('%d %d %d\n' % (ob.rows, ob.columns, last_elt))

	# Output all rows except last
	for i in range(ob.rows-1):
	    rd = ob.get_row_dict(i)
	    for j, value in sorted(rd.items()):
		file.write('%d %d %f\n' % (i+1, j+1, value))

	# Now the last row, except for the element that was already
	# output.
	rd = ob.get_row_dict(ob.rows-1)
	for j, value in sorted(rd.items()):
	    if j != ob.columns-1:
		file.write('%d %d %f\n' % (i+1, j+1, value))

    def write_binary(self, file, ob):
	# Start by outputting bottom-right element, defining the size
	# of the matrix.
	last_elt = ob.get_sparse_row(ob.rows-1)[-1]
	if last_elt == ob.columns-1:
	    elt = 1
	else:
	    elt = 0
	file.write('%d %d %d\n' % (ob.rows, ob.columns, elt))

	# Output all rows except last
	for i in range(ob.rows-1):
	    datarow = ob.get_sparse_row(i)
	    for j in datarow:
		file.write('%d %d 1\n' % (i+1, j+1))

	# Now the last row, except for the element that was already
	# output.
	datarow = ob.get_sparse_row(ob.rows-1)
	if datarow[-1] == ob.columns-1:
	    datarow = datarow[:-1]
	for j in datarow:
	    file.write('%d %d 1\n' % (ob.rows, j+1))

class Arff(FileFormat):
    
    def _autodetect(self, file, fast):
        if fast: limit = 100
        else: limit = float('inf')
        
        lineno = 0;
        while lineno < limit:
            line = file.readline ()
            lineno += 1
            if line == '': break
            if line.startswith ('@relation'):
                return 1
        return 0
    
    def read(self, file):
        matrix = ArffMatrix()
        i = 0
        dictionary = []
        while True:
            line = file.readline()
            if line.startswith ('%'):
                continue
            if line.startswith ('@relation' ):
                continue
            if line.startswith ('@attribute' ):
                fields = line.split ()
            if line.startswith ('@data' ):
                break
            range=fields[2:]   
            dictionary.append([fields[1],range])
        matrix.dictionary = dictionary
        while True:
            line = file.readline()
            if line == "":
                break
            line = line.strip ().split (",")
            if len(line) != len(dictionary):
                errmsg = "syntax error"
                raise TypeError, errmsg
            matrix.data.append ( line )
        return matrix
    
    def write_arff(self,file,ob):
        file.write('@relation iq\n')
        for i in ob.dictionary:
            name, type = i[0], i[1]
            file.write('@attribute ' + name + ' ' + ' '.join(val for val in type) + '\n' )
        file.write('@data\n')
        for i in ob.data:
            file.write(','.join(str(value) for value in i))
            file.write('\n')
        
    def write_binary(self, file, ob):
        file.write('@relation iq\n')
        
        for i in range(ob.columns):
            file.write('@attribute a' + str(i) + ' {0,1}\n')
        file.write('@data\n')
        for i in range(ob.rows):
          newrow = [ "0" for x in range(ob.columns)]
          row = ob.get_sparse_row(i)
          for i in row: newrow[i] = "1"
          file.write(','.join(newrow))
          file.write('\n')  
          
    def write_real(self,file,ob):
        file.write('@relation iq\n')
        
        for i in range(ob.columns):
            file.write('@attribute a' + str(i) + ' {0,1}\n')
        file.write('@data\n')
        for i in range(ob.rows):
          row = ob.get_row(i)
          file.write(','.join([string(i) for i in row]))
          file.write('\n')  
        

class Fimi(FileFormat):
    """This is like the Iq sparse boolean format without the header."""

    def _autodetect(self, file, fast):
	if fast: limit = 100
	else: limit = float('inf')

	lineno = 0
	while lineno < limit:
	    line = file.readline()
	    lineno += 1
	    if line == '': break
	    try: 
		fields = [ int(x) for x in line.split() ]
	    except: 
		debug("impossible fimi line:", line)
		return 0
	    if not strictly_increasing(fields): 
		debug("not strictly increasing:", line)
		return 0

	if lineno == 0: return 0
	if not fast: return 1
	return float(file.tell()) / os.fstat(file.fileno())[stat.ST_SIZE]

    def read(self, file):
	matrix = BinaryMatrix()
	i = 0
	while True:
	    line = file.readline()
	    if line == '':
		return matrix

	    line.strip()
	    data = line.split()
	    if data == ['']:
		data = []
	    data = [ int(x) for x in data ]

	    try: newcols = max(data)+1
	    except ValueError: newcols = 1
	    matrix.enlarge(i+1, newcols)
	    matrix.set_sparse_row(i, data)
	    i += 1
    
    def write_binary(self, file, ob):
	for i in range(ob.rows):
	    row = ob.get_sparse_row(i)
	    row = [ str(x) for x in row ]
	    file.write(' '.join(row))
	    file.write('\n')

formats = { "iq": Iq(), 
	    "spconvert": Spconvert(), 
	    "fimi": Fimi(),
        "arff": Arff() }

def autodetect(file):
    max, winner, max_unique = 0, None, False
    formats_left = copy.copy(formats)
    for fast in True, False:
	items = formats_left.items()
	for name, format in items:
	    likelihood = format.autodetect(file, fast)
	    if likelihood == 1: return name
	    if likelihood == 0: del formats_left[name]
	    if likelihood > max:
		max, winner, max_unique = likelihood, name, True
	    elif likelihood == max:
		max_unique = False
	if max_unique: break

    return winner

def convert(informat, infile, outformat, outfile):
    if isinstance(informat, (str, unicode)):
        informat = formats[informat]
    if isinstance(outformat, (str, unicode)):
        outformat = formats[outformat]

    inhandle = open(infile, 'rb')
    data = informat.read(inhandle)
    inhandle.close()
    debug("data type:", data.__class__)

    outhandle = open(outfile, 'wb')
    outformat.write(outhandle, data)
    outhandle.close()

